package com.uhu.code;

import com.uhu.code.help.ListNode;

/**
 * 25. K 个一组翻转链表
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) {
            return head;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        for(int i = 1; i < k; i++) {
            fastNode = fastNode.next;
        }
        ListNode result = fastNode;

        ListNode slowTempNode = slowNode;
        ListNode fastTempNode = fastNode;
        ListNode nextStartNode = null;
        while(fastNode != null) {
            if(slowNode == fastTempNode) {
                ListNode startNode = slowTempNode;
                ListNode endNextNode = fastTempNode.next;
                ListNode newHead = reverse(slowTempNode, fastTempNode);
                if(nextStartNode != null) {
                    nextStartNode.next = newHead;
                }
                nextStartNode = startNode;
                startNode.next = endNextNode;
                slowTempNode = slowNode.next;
                fastTempNode = fastNode.next;
            }
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        return result;
    }

    private ListNode reverse(ListNode slowTempNode, ListNode fastTempNode) {
        if(slowTempNode == fastTempNode) {
            // 递归结束
            return slowTempNode;
        }else {
            ListNode newHead = reverse(slowTempNode.next, fastTempNode);
            slowTempNode.next.next = slowTempNode;
            slowTempNode.next = null;
            return newHead;
        }
    }
}
